// https://www.lintcode.com/problem/minimum-path-sum/description

class Solution {
public:
    /**
     * @param grid: a list of lists of integers
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    // int minPathSum(vector<vector<int>> &grid) {
    //     if (grid.empty()) return 0;
    //     int m = grid.size();
    //     int n = grid[0].size();
    //     vector<vector<int>> res(m, vector<int>(n, 0));
    //     res[0][0] = grid[0][0];
    //     for (int i = 1; i < m; ++i)
    //     {
    //         res[i][0] = res[i - 1][0] + grid[i][0];
    //     }
    //     for (int j = 1; j < n; ++j)
    //     {
    //         res[0][j] = res[0][j - 1] + grid[0][j];
    //     }
    //     for (int i = 1; i < m; ++i)
    //     {
    //         for (int j = 1; j < n; ++j)
    //         {
    //             res[i][j] = min(res[i - 1][j], res[i][j - 1]) + grid[i][j];
    //         }
    //     }
    //     return res[m - 1][n - 1];
    // }
    
    //另一种写法
    // int minPathSum(vector<vector<int>> &grid) {
    //     if (grid.empty()) return 0;
    //     int m = grid.size();
    //     int n = grid[0].size();
    //     vector<vector<int>> res(m, vector<int>(n, INT_MAX));
    //     for (int i = 0; i < m; ++i)
    //     {
    //         for (int j = 0; j < n; ++j)
    //         {
    //             if (i == 0 && j == 0)
    //             {
    //                 res[i][j] = grid[0][0];
    //                 continue;
    //             }
    //             if (i > 0) res[i][j] = min(res[i][j], res[i - 1][j] + grid[i][j]);
    //             if (j > 0) res[i][j] = min(res[i][j], res[i][j - 1] + grid[i][j]);
    //         }
    //     }
    //     return res[m - 1][n - 1];
    // }
    
    // // 动态规划打印路径
    // int minPathSum(vector<vector<int>> &grid) {
    //     if (grid.empty()) return 0;
    //     int m = grid.size();
    //     int n = grid[0].size();
    //     vector<vector<int>> res(m, vector<int>(n, INT_MAX));
    //     vector<vector<int>> record(m, vector<int>(n));
    //     for (int i = 0; i < m; ++i)
    //     {
    //         for (int j = 0; j < n; ++j)
    //         {
    //             if (i == 0 && j == 0)
    //             {
    //                 res[i][j] = grid[0][0];
    //                 continue;
    //             }
    //             if (i > 0) 
    //             {
    //                 res[i][j] = min(res[i][j], res[i - 1][j] + grid[i][j]);
    //                 if (res[i][j] == res[i - 1][j] + grid[i][j]) record[i][j] = 0; 
    //             }
    //             if (j > 0) 
    //             {
    //                 res[i][j] = min(res[i][j], res[i][j - 1] + grid[i][j]);
    //                 if (res[i][j] == res[i][j - 1] + grid[i][j]) record[i][j] = 1;
    //             }
    //         }
    //     }
    //     vector<vector<int>> path(m + n - 1, vector<int>(2));
    //     int i = m - 1;
    //     int j = n - 1;
    //     for (int p = m + n - 2; p >= 0; --p)
    //     {
    //         path[p][0] = i;
    //         path[p][1] = j;
    //         if (record[i][j] == 0) i--;
    //         else j--;
    //     }
    //     for (int p = 0; p < m + n - 1; ++p)
    //     {
    //         cout << "(" << path[p][0] << "," << path[p][1] << "):" 
    //         << grid[path[p][0]][path[p][1]] << endl;
    //     }
    //     return res[m - 1][n - 1];
    // }
    
    
    // 滚动数组优化空间复杂度为O(N)
    int minPathSum(vector<vector<int>> &grid) {
        if (grid.empty()) return 0;
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> res(2, vector<int>(n));
        int now = 0;
        int pre = 0;
        for (int i = 0; i < m; ++i)
        {
            pre = now;
            now = 1 - now; // 比%2快一些
            for (int j = 0; j < n; ++j)
            {
                if (i == 0 && j == 0)
                {
                    res[now][j] = grid[0][0];
                    continue;
                }
                res[now][j] = INT_MAX; //滚动数组需要重新赋值！一开始初始化没用
                if (i > 0) 
                {
                    res[now][j] = min(res[now][j], res[pre][j]);
                }
                if (j > 0) 
                {
                    res[now][j] = min(res[now][j], res[now][j - 1]);
                }
                res[now][j] += grid[i][j];
                cout << i << " " << j << " " << res[now][j] << endl;
            }
        }
        return res[now][n - 1];
    }
    
    
    // 如果是可以任意走，就只能用搜索的方法
};